package com.qimingyu.recursion;

import java.util.Arrays;

/**
 * @author doreaxon
 * @version 1.0
 * @date 2023/9/7 21:20
 * @注释 递归实现冒泡排序
 */
public class BubbleSortWithRecursion {

    /**
     * 冒泡排序的入口方法，接受一个整型数组作为参数。
     * 该方法调用了bubbleSortWithRecursion(int right, int arr[])方法进行排序。
     * @param arr 待排序的整型数组
     */
    public static void bubble(int arr[]) {
        bubbleSortWithRecursion(arr.length - 1, arr);
    }

    /**
     * 递归实现冒泡排序的方法，接受两个参数：右边界right和待排序的整型数组arr。
     * 如果右边界小于等于0，则直接返回；否则，通过一个循环遍历数组中的元素，如果发现当前元素大于后一个元素，就交换它们的位置。
     * 然后，递归调用bubbleSortWithRecursion(right - 1, arr)方法，将右边界减1，继续对剩余的元素进行排序。
     * @param right 右边界
     * @param arr 待排序的整型数组
     */
    public static void bubbleSortWithRecursion(int right, int[] arr) {
        if (right <= 0) {
            return;
        }
        int x = 0;
        for (int i = 0; i < right; i++) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                /*
                x用于记录这次递归中最后一次的交换中i的所在位置
                x即为有序和无序的分界线，x的右边是有序的，x以及其左边是无序的，所以下次遍历直接以x为右边界即可
                */
                x = i;
            }
        }
        bubbleSortWithRecursion(x, arr);
    }

    /**
     * 程序的入口方法，不接受任何参数。
     * 在该方法中，定义了一个整型数组arr并初始化为{9, 2, 5, 6, 3, 0, 1}。
     * 然后调用了bubble(arr)方法对数组进行排序。
     * 最后，使用System.out.println(Arrays.toString(arr))打印出排序后的数组。
     * @param args 命令行参数
     */
    public static void main(String[] args) {
        int arr[] = {9, 2, 5, 6, 3, 0, 1};
        bubble(arr);
        System.out.println(Arrays.toString(arr));
    }
}
